Multiprocessor Scheduling of Dependent Tasks to Minimize Makespan and Reliability Cost Using NSGA-II

摘要

Algorithms developed for scheduling applications on heterogeneousmultiprocessor system focus on asingle objective such as execution time, costor total data transmission time. However, if more than oneobjective (e.g.execution cost and time, which may be in conflict) are considered, then theproblem becomes more challenging. This project is proposed to develop amultiobjective scheduling algorithm using Evolutionary techniques forscheduling a set of dependent tasks on available resources in a multiprocessorenvironment which will minimize the makespan and reliability cost. ANon-dominated sorting Genetic Algorithm-II procedure has been developed to getthe pareto- optimal solutions. NSGA-II is a Elitist Evolutionary algorithm, andit takes the initial parental solution without any changes, in all iteration toeliminate the problem of loss of some pareto-optimal solutions.NSGA-II usescrowding distance concept to create a diversity of the solutions.